home *** CD-ROM | disk | FTP | other *** search
/ 17 Bit Software 6: Level 6 / 17 Bit - Level 6 (1998)(Epic Marketing)[!].iso / quartz / q0429.dms / q0429.adf / libray / libobj / hf.c < prev    next >
C/C++ Source or Header  |  1992-05-20  |  17KB  |  741 lines
  1. /*
  2.  * hf.c
  3.  *
  4.  * Copyright (C) 1989, 1991, Craig E. Kolb
  5.  * All rights reserved.
  6.  *
  7.  * This software may be freely copied, modified, and redistributed
  8.  * provided that this copyright notice is preserved on all copies.
  9.  *
  10.  * You may not distribute this software, in whole or in part, as part of
  11.  * any commercial product without the express consent of the authors.
  12.  *
  13.  * There is no warranty or other guarantee of fitness of this software
  14.  * for any purpose.  It is provided solely "as is".
  15.  *
  16.  * $Id: hf.c,v 4.0.1.1 91/09/29 15:44:53 cek Exp Locker: cek $
  17.  *
  18.  * $Log:    hf.c,v $
  19.  * Revision 4.0.1.1  91/09/29  15:44:53  cek
  20.  * patch1: Error messages missing newline.
  21.  * 
  22.  * Revision 4.0  91/07/17  14:38:15  kolb
  23.  * Initial version.
  24.  * 
  25.  */
  26. #include "geom.h"
  27. #include "hf.h"
  28.  
  29. static Methods *iHfMethods = NULL;
  30. static char hfName[] = "heighfield";
  31.  
  32. static void integrate_grid(), QueueTri();
  33. static int DDA2D(), CheckCell();
  34. static Float intHftri();
  35. static float minalt(), maxalt();
  36.  
  37. typedef struct {
  38.     int stepX, stepY;
  39.     Float tDX, tDY;
  40.     float minz, maxz;
  41.     int outX, outY;
  42.     Vector cp, pDX, pDY;
  43. } Trav2D;
  44.  
  45. hfTri *CreateHfTriangle(), *GetQueuedTri();
  46.  
  47. unsigned long HFTests, HFHits;
  48.  
  49. Hf *
  50. HfCreate(filename)
  51. char *filename;
  52. {
  53.     Hf *hf;
  54.     FILE *fp;
  55.     float val, *maxptr, *minptr;
  56.     int i, j;
  57.  
  58.     fp = fopen(filename, "r");
  59.     if (fp == (FILE *)NULL) {
  60.         RLerror(RL_ABORT, "Cannot open heightfield file \"%s\".\n",
  61.                 filename);
  62.         return (Hf *)NULL;
  63.     }
  64.  
  65.     hf = (Hf *)Malloc(sizeof(Hf));
  66.     /*
  67.      * Make the following an option someday.
  68.      */
  69.     hf->BestSize = BESTSIZE;
  70.     /*
  71.      * Store the inverse for faster computation.
  72.      */
  73.     hf->iBestSize = 1. / (float)hf->BestSize;
  74.     /*
  75.      * Get HF size.
  76.      */
  77.     if (fread((char *)&hf->size, sizeof(int), 1, fp) == 0) {
  78.         RLerror(RL_ABORT, "Cannot read height field size.\n");
  79.         return (Hf *)NULL;
  80.     }
  81.         
  82.     hf->data = (float **)share_malloc(hf->size * sizeof(float *));
  83.     for (i = 0; i < hf->size; i++) {
  84.         hf->data[i] = (float *)share_malloc(hf->size * sizeof(float));
  85.         /*
  86.          * Read in row of HF data.
  87.          */
  88.         if (fread((char *)hf->data[i],sizeof(float),hf->size,fp)
  89.             != hf->size) {
  90.             RLerror(RL_ABORT, "Not enough heightfield data.\n");
  91.             return (Hf *)NULL;
  92.         }
  93.         for (j = 0; j < hf->size; j++) {
  94.             val = hf->data[i][j];
  95.             if (val <= HF_UNSET) {
  96.                 hf->data[i][j] = HF_UNSET;
  97.                 /*
  98.                  * Don't include the point in min/max
  99.                  * calculations.
  100.                  */
  101.                 continue;
  102.             }
  103.             if (val > hf->maxz)
  104.                 hf->maxz = val;
  105.             if (val < hf->minz)
  106.                 hf->minz = val;
  107.         }
  108.     }
  109.     (void)fclose(fp);
  110.     /*
  111.      * Allocate levels of grid.  hf->levels = log base BestSize of hf->size
  112.      */
  113.     for (i = hf->size, hf->levels = 0; i > hf->BestSize; i /= hf->BestSize,
  114.                 hf->levels++)
  115.             ;
  116.     hf->levels++;
  117.     hf->qsize = CACHESIZE;
  118.     hf->q = (hfTri **)Calloc((unsigned)hf->qsize, sizeof(hfTri *));
  119.     hf->qtail = 0;
  120.  
  121.     hf->lsize = (int *)share_malloc(hf->levels * sizeof(int));
  122.     hf->spacing = (float *)share_malloc(hf->levels * sizeof(float));
  123.     hf->boundsmax = (float ***)share_malloc(hf->levels * sizeof(float **));
  124.     hf->boundsmin = (float ***)share_malloc(hf->levels * sizeof(float **));
  125.  
  126.     hf->spacing[0] = hf->size -1;
  127.     hf->lsize[0] = (int)hf->spacing[0];
  128.     hf->boundsmax[0] = (float **)share_malloc(hf->lsize[0]*sizeof(float *));
  129.     hf->boundsmin[0] = (float **)share_malloc(hf->lsize[0]*sizeof(float *));
  130.     /*
  131.      * Compute initial bounding boxes
  132.      */
  133.     for (i = 0; i < hf->lsize[0]; i++) {
  134.         hf->boundsmax[0][i]=(float *)share_malloc(hf->lsize[0]*sizeof(float));
  135.         hf->boundsmin[0][i]=(float *)share_malloc(hf->lsize[0]*sizeof(float));
  136.         maxptr = hf->boundsmax[0][i];
  137.         minptr = hf->boundsmin[0][i];
  138.         for (j = 0; j < hf->lsize[0]; j++) {
  139.             *maxptr++ = maxalt(i, j, hf->data) + EPSILON;
  140.             *minptr++ = minalt(i, j, hf->data) - EPSILON;
  141.         }
  142.     }
  143.  
  144.     for (i = 1; i < hf->levels; i++) {
  145.         hf->spacing[i] = hf->spacing[i-1] * hf->iBestSize;
  146.         hf->lsize[i] = (int)hf->spacing[i];
  147.         if ((Float)hf->lsize[i] != hf->spacing[i])
  148.             hf->lsize[i]++;
  149.         hf->boundsmax[i]=(float **)share_malloc(hf->lsize[i]*sizeof(float *));
  150.         hf->boundsmin[i]=(float **)share_malloc(hf->lsize[i]*sizeof(float *));
  151.         for (j = 0; j < hf->lsize[i]; j++) {
  152.             hf->boundsmax[i][j] = (float *)share_malloc(hf->lsize[i] *
  153.                             sizeof(float));
  154.             hf->boundsmin[i][j] = (float *)share_malloc(hf->lsize[i] *
  155.                             sizeof(float));
  156.         }
  157.         integrate_grid(hf, i);
  158.     }
  159.  
  160.     hf->boundbox[LOW][X] = hf->boundbox[LOW][Y] = 0;
  161.     hf->boundbox[HIGH][X] = hf->boundbox[HIGH][Y] = 1;
  162.     hf->boundbox[LOW][Z] = hf->minz;
  163.     hf->boundbox[HIGH][Z] = hf->maxz;
  164.  
  165.     return hf;
  166. }
  167.  
  168. Methods *
  169. HfMethods()
  170. {
  171.     if (iHfMethods == (Methods *)NULL) {
  172.         iHfMethods = MethodsCreate();
  173.         iHfMethods->create = (GeomCreateFunc *)HfCreate;
  174.         iHfMethods->methods = HfMethods;
  175.         iHfMethods->name = HfName;
  176.         iHfMethods->intersect = HfIntersect;
  177.         iHfMethods->normal = HfNormal;
  178.         iHfMethods->uv = HfUV;
  179.         iHfMethods->bounds = HfBounds;
  180.         iHfMethods->stats = HfStats;
  181.         iHfMethods->checkbounds = TRUE;
  182.         iHfMethods->closed = FALSE;
  183.     }
  184.     return iHfMethods;
  185. }
  186.  
  187. /*
  188.  * Intersect ray with height field.
  189.  */
  190. int
  191. HfIntersect(hf, ray, mindist, maxdist)
  192. Hf *hf;
  193. Ray *ray;
  194. Float mindist, *maxdist;
  195. {
  196.     Vector hitpos;
  197.     Float offset;
  198.     Trav2D trav;
  199.  
  200.     HFTests++;
  201.  
  202.     /*
  203.      * Find where we hit the hf cube.
  204.      */
  205.     VecAddScaled(ray->pos, mindist, ray->dir, &hitpos);
  206.     if (OutOfBounds(&hitpos, hf->boundbox)) {
  207.         offset = *maxdist;
  208.         if (!BoundsIntersect(ray, hf->boundbox, mindist, &offset))
  209.             return FALSE;
  210.         hitpos.x = ray->pos.x + ray->dir.x * offset;
  211.         hitpos.y = ray->pos.y + ray->dir.y * offset;
  212.         hitpos.z = ray->pos.z + ray->dir.z * offset;
  213.     } else
  214.         hitpos = ray->pos;
  215.     /*
  216.      * Find out in which cell "hitpoint" is.
  217.      */
  218.     if (equal(hitpos.x, 1.))
  219.         hitpos.x -= EPSILON;
  220.     if (equal(hitpos.y, 1.))
  221.         hitpos.y -= EPSILON;
  222.  
  223.     if (ray->dir.x < 0.) {
  224.         trav.stepX = trav.outX = -1;
  225.         trav.tDX = -1. / (ray->dir.x * hf->spacing[hf->levels -1]);
  226.     } else if (ray->dir.x > 0.) {
  227.         trav.stepX = 1;
  228.         trav.outX = hf->lsize[hf->levels -1];
  229.         /*
  230.          * (1./size) / ray
  231.          */
  232.         trav.tDX = 1. / (ray->dir.x * hf->spacing[hf->levels -1]);
  233.     }
  234.  
  235.     if (ray->dir.y < 0.) {
  236.         trav.stepY = trav.outY = -1;
  237.         trav.tDY = -1. / (ray->dir.y * hf->spacing[hf->levels -1]);
  238.     } else if (ray->dir.y > 0.) {
  239.         trav.stepY = 1;
  240.         trav.outY = hf->lsize[hf->levels -1];
  241.         trav.tDY = 1. / (ray->dir.y * hf->spacing[hf->levels -1]);
  242.     }
  243.  
  244.     trav.pDX.x = ray->dir.x * trav.tDX;
  245.     trav.pDX.y = ray->dir.y * trav.tDX;
  246.     trav.pDX.z = ray->dir.z * trav.tDX;
  247.     trav.pDY.x = ray->dir.x * trav.tDY;
  248.     trav.pDY.y = ray->dir.y * trav.tDY;
  249.     trav.pDY.z = ray->dir.z * trav.tDY;
  250.  
  251.     trav.cp = hitpos;
  252.     trav.minz = hf->minz;
  253.     trav.maxz = hf->maxz;
  254.     if (DDA2D(hf, &ray->pos, &ray->dir, hf->levels -1, &trav, maxdist)) {
  255.         HFHits++;
  256.         return TRUE;
  257.     }
  258.     return FALSE;
  259. }
  260.  
  261. /*
  262.  * Traverse the grid using a modified DDA algorithm.  If the extent of
  263.  * the ray over a cell intersects the bounding volume defined by the
  264.  * four corners of the cell, either recurse or perform ray/surface
  265.  * intersection test.
  266.  */
  267. static int
  268. DDA2D(hf, pos, ray, level, trav, maxdist)
  269. Hf *hf;
  270. Vector *pos, *ray;
  271. int level;
  272. Trav2D *trav;
  273. Float *maxdist;
  274. {
  275.     int x, y, size, posZ;
  276.     float **boundsmin, **boundsmax, spacing;
  277.     Float tX, tY;
  278.     Trav2D newtrav;
  279.     Vector nxp, nyp;
  280.  
  281.     size = hf->lsize[level];
  282.     spacing = hf->spacing[level];
  283.  
  284.     posZ = (ray->z > 0.);
  285.  
  286.     x = trav->cp.x * hf->spacing[level];
  287.     if (x == size)
  288.         x--;
  289.     y = trav->cp.y * hf->spacing[level];
  290.     if (y == size)
  291.         y--;
  292.     boundsmax = hf->boundsmax[level];
  293.     boundsmin = hf->boundsmin[level];
  294.  
  295.     if (trav->outX > size) trav->outX = size;
  296.     if (trav->outY > size) trav->outY = size;
  297.     if (trav->outX < 0) trav->outX = -1;
  298.     if (trav->outY < 0) trav->outY = -1;
  299.  
  300.     if (ray->x < 0.) {
  301.         tX = (x /spacing - trav->cp.x) / ray->x;
  302.     } else if (ray->x > 0.)
  303.         tX = ((x+1)/spacing - trav->cp.x) / ray->x;
  304.     else
  305.         tX = FAR_AWAY;
  306.     if (ray->y < 0.) {
  307.         tY = (y /spacing - trav->cp.y) / ray->y;
  308.     } else if (ray->y > 0.)
  309.         tY = ((y+1)/spacing - trav->cp.y) / ray->y;
  310.     else
  311.         tY = FAR_AWAY;
  312.  
  313.     nxp.x = trav->cp.x + tX * ray->x;
  314.     nxp.y = trav->cp.y + tX * ray->y;
  315.     nxp.z = trav->cp.z + tX * ray->z;
  316.  
  317.     nyp.x = trav->cp.x + tY * ray->x;
  318.     nyp.y = trav->cp.y + tY * ray->y;
  319.     nyp.z = trav->cp.z + tY * ray->z;
  320.  
  321.     do {
  322.         if (tX < tY) {
  323.             if ((posZ && trav->cp.z <= boundsmax[y][x] &&
  324.                  nxp.z >= boundsmin[y][x]) ||
  325.                 (!posZ && trav->cp.z >= boundsmin[y][x] &&
  326.                  nxp.z <= boundsmax[y][x])) {
  327.                 if (level) {
  328.                     /*
  329.                      * Recurse -- compute constants
  330.                      * needed for next level.
  331.                      * Nicely enough, this just
  332.                      * involves a few multiplications.
  333.                      */
  334.                     newtrav = *trav;
  335.                     newtrav.tDX *= hf->iBestSize;
  336.                     newtrav.tDY *= hf->iBestSize;
  337.                     newtrav.maxz = boundsmax[y][x];
  338.                     newtrav.minz = boundsmin[y][x];
  339.                     if (ray->x < 0.)
  340.                         newtrav.outX=hf->BestSize*x-1;
  341.                     else
  342.                         newtrav.outX=hf->BestSize*(x+1);
  343.                     if (ray->y < 0.)
  344.                         newtrav.outY=hf->BestSize*y-1;
  345.                     else
  346.                         newtrav.outY=hf->BestSize*(y+1);
  347.                     newtrav.pDX.x *= hf->iBestSize;
  348.                     newtrav.pDX.y *= hf->iBestSize;
  349.                     newtrav.pDX.z *= hf->iBestSize;
  350.                     newtrav.pDY.x *= hf->iBestSize;
  351.                     newtrav.pDY.y *= hf->iBestSize;
  352.                     newtrav.pDY.z *= hf->iBestSize;
  353.                     if (DDA2D(hf,pos,ray,level-1,
  354.                         &newtrav, maxdist))
  355.                         return TRUE;
  356.                 } else if (CheckCell(x,y,hf,ray,pos,maxdist))
  357.                     return TRUE;
  358.             }
  359.             x += trav->stepX;        /* Move in X */
  360.             if (*maxdist < tX || x == trav->outX)
  361.                 /* If outside, quit */
  362.                 return FALSE;
  363.             tX += trav->tDX;    /* Update position on ray */
  364.             trav->cp = nxp;        /* cur pos gets next pos */
  365.             nxp.x += trav->pDX.x;    /* Compute next pos */
  366.             nxp.y += trav->pDX.y;
  367.             nxp.z += trav->pDX.z;
  368.         } else {
  369.             if ((posZ && trav->cp.z <= boundsmax[y][x] &&
  370.                  nyp.z >= boundsmin[y][x]) ||
  371.                 (!posZ && trav->cp.z >= boundsmin[y][x] &&
  372.                  nyp.z <= boundsmax[y][x])) {
  373.                 if (level) {
  374.                     /* Recurse */
  375.                     newtrav = *trav;
  376.                     newtrav.tDX *= hf->iBestSize;
  377.                     newtrav.tDY *= hf->iBestSize;
  378.                     newtrav.maxz = boundsmax[y][x];
  379.                     newtrav.minz = boundsmin[y][x];
  380.                     if (ray->x < 0.)
  381.                         newtrav.outX=hf->BestSize*x-1;
  382.                     else
  383.                         newtrav.outX=hf->BestSize*(x+1);
  384.                     if (ray->y < 0.)
  385.                         newtrav.outY=hf->BestSize*y-1;
  386.                     else
  387.                         newtrav.outY=hf->BestSize*(y+1);
  388.                     newtrav.pDX.x *= hf->iBestSize;
  389.                     newtrav.pDX.y *= hf->iBestSize;
  390.                     newtrav.pDX.z *= hf->iBestSize;
  391.                     newtrav.pDY.x *= hf->iBestSize;
  392.                     newtrav.pDY.y *= hf->iBestSize;
  393.                     newtrav.pDY.z *= hf->iBestSize;
  394.                     if (DDA2D(hf,pos,ray,level-1,
  395.                             &newtrav, maxdist))
  396.                         return TRUE;
  397.                 } else if (CheckCell(x,y,hf,ray,pos,maxdist))
  398.                     return TRUE;
  399.             }
  400.             y += trav->stepY;
  401.             if (*maxdist < tY || y == trav->outY)
  402.                 return FALSE;
  403.             tY += trav->tDY;
  404.             trav->cp = nyp;
  405.             nyp.x += trav->pDY.x;
  406.             nyp.y += trav->pDY.y;
  407.             nyp.z += trav->pDY.z;
  408.         }
  409.     } while ((trav->cp.x <= 1. && trav->cp.y <= 1.) &&
  410.          ((posZ && trav->cp.z <= trav->maxz) ||
  411.          (!posZ && trav->cp.z >= trav->minz)));
  412.  
  413.         /*
  414.          * while ((we're inside the horizontal bounding box)
  415.          *        (usually caught by outX & outY, but
  416.          *         it's possible to go "too far" due to
  417.          *         the fact that our levels of grids do
  418.          *         not "nest" exactly if gridsize%BestSize != 0)
  419.          *      and
  420.          *      ((if ray->z is positive and we haven't gone through
  421.          *       the upper bounding plane) or
  422.          *      (if ray->z is negative and we haven't gone through
  423.          *       the lower bounding plane)));
  424.          */
  425.  
  426.     return FALSE;
  427. }
  428.  
  429. /*
  430.  * Check for ray/cell intersection
  431.  */
  432. static int
  433. CheckCell(x, y, hf, ray, pos, maxdist)
  434. int x, y;
  435. Hf *hf;
  436. Vector *ray, *pos;
  437. Float *maxdist;
  438. {
  439.     hfTri *tri1, *tri2;
  440.     Float d1, d2;
  441.  
  442.     d1 = d2 = FAR_AWAY;
  443.  
  444.     if (tri1 = CreateHfTriangle(hf, x, y, x+1, y, x, y+1, TRI1))
  445.         d1 = intHftri(ray, pos, tri1);
  446.     if (tri2 = CreateHfTriangle(hf, x+1, y, x+1, y+1, x, y+1, TRI2))
  447.         d2 = intHftri(ray, pos, tri2);
  448.  
  449.     if (d1 == FAR_AWAY && d2 == FAR_AWAY)
  450.         return FALSE;
  451.  
  452.     if (d1 < d2) {
  453.         if (d1 < *maxdist) {
  454.             hf->hittri = *tri1;
  455.             *maxdist = d1;
  456.             return TRUE;
  457.         }
  458.         return FALSE;
  459.     }
  460.  
  461.     if (d2 < *maxdist) {
  462.         hf->hittri = *tri2;
  463.         *maxdist = d2;
  464.         return TRUE;
  465.     }
  466.     return FALSE;
  467. }
  468.  
  469. static hfTri *
  470. CreateHfTriangle(hf, x1, y1, x2, y2, x3, y3, which)
  471. Hf *hf;
  472. int x1, y1, x2, y2, x3, y3, which;
  473. {
  474.     hfTri *tri;
  475.     Float xid, yid;
  476.     Vector tmp1, tmp2;
  477.  
  478.     /*
  479.      * Don't use triangles with "unset" vertices.
  480.      */
  481.     if (hf->data[y1][x1] == HF_UNSET ||
  482.         hf->data[y2][x2] == HF_UNSET ||
  483.         hf->data[y3][x3] == HF_UNSET)
  484.         return (hfTri *)0;
  485.  
  486.     xid = (Float)x1 / (Float)(hf->size -1);
  487.     yid = (Float)y1 / (Float)(hf->size -1);
  488.  
  489.     if ((tri = GetQueuedTri(hf, xid, yid, which)) != (hfTri *)0)
  490.         return tri;
  491.  
  492.     tri = (hfTri *)Malloc(sizeof(hfTri));
  493.  
  494.     tri->type = which;
  495.     tri->v1.x = xid;
  496.     tri->v1.y = yid;
  497.     tri->v1.z = hf->data[y1][x1];
  498.     tri->v2.x = (Float)x2 / (Float)(hf->size-1);
  499.     tri->v2.y = (Float)y2 / (Float)(hf->size-1);
  500.     tri->v2.z = hf->data[y2][x2];
  501.     tri->v3.x = (Float)x3 / (Float)(hf->size-1);
  502.     tri->v3.y = (Float)y3 / (Float)(hf->size-1);
  503.     tri->v3.z = hf->data[y3][x3];
  504.  
  505.     tmp1.x = tri->v2.x - tri->v1.x;
  506.     tmp1.y = tri->v2.y - tri->v1.y;
  507.     tmp1.z = tri->v2.z - tri->v1.z;
  508.     tmp2.x = tri->v3.x - tri->v1.x;
  509.     tmp2.y = tri->v3.y - tri->v1.y;
  510.     tmp2.z = tri->v3.z - tri->v1.z;
  511.  
  512.     (void)VecNormCross(&tmp1, &tmp2, &tri->norm);
  513.  
  514.     tri->d = -dotp(&tri->v1, &tri->norm);
  515.  
  516.     QueueTri(hf, tri);
  517.     return tri;
  518. }
  519.  
  520. /*
  521.  * Intersect ray with right isoscoles triangle, the hypotenuse of which
  522.  * has slope of -1.
  523.  */
  524. static Float
  525. intHftri(ray, pos, tri)
  526. hfTri *tri;
  527. Vector *pos, *ray;
  528. {
  529.     Float u, v, dist, xpos, ypos;
  530.  
  531.     u = dotp(&tri->norm, pos) + tri->d;
  532.     v = dotp(&tri->norm, ray);
  533.  
  534.     if ((u <= 0. || v > -EPSILON) && (u >= 0. && v < EPSILON))
  535.         return FAR_AWAY;
  536.  
  537.     dist = -u / v;
  538.  
  539.     if (dist < EPSILON)
  540.         return FAR_AWAY;
  541.  
  542.     xpos = pos->x + dist*ray->x;
  543.     ypos = pos->y + dist*ray->y;
  544.  
  545.     if (tri->type == TRI1 && xpos >= tri->v1.x && ypos >= tri->v1.y &&
  546.         xpos + ypos <= tri->v2.x + tri->v2.y)
  547.         return dist;
  548.     if (tri->type == TRI2 && xpos <= tri->v2.x && ypos <= tri->v2.y &&
  549.         xpos + ypos >= tri->v1.x + tri->v1.y)
  550.         return dist;
  551.     return FAR_AWAY;
  552. }
  553.  
  554. /*
  555.  * Compute normal to height field.
  556.  */
  557. /*ARGSUSED*/
  558. int
  559. HfNormal(hf, pos, nrm, gnrm)
  560. Hf *hf;
  561. Vector *pos, *nrm, *gnrm;
  562. {
  563.     *gnrm = *nrm = hf->hittri.norm;
  564.     return FALSE;
  565. }
  566.  
  567. /*ARGSUSED*/
  568. void
  569. HfUV(hf, pos, norm, uv, dpdu, dpdv)
  570. Hf *hf;
  571. Vector *pos, *norm, *dpdu, *dpdv;
  572. Vec2d *uv;
  573. {
  574.     uv->u = pos->x;
  575.     uv->v = pos->y;
  576.     if (dpdu) {
  577.         dpdu->x = 1.;
  578.         dpdu->y = dpdv->z = 0.;
  579.         dpdv->x = dpdv->z = 0.;
  580.         dpdv->y = 1.;
  581.     }
  582. }
  583.  
  584. /*
  585.  * Compute heightfield bounding box.
  586.  */
  587. void
  588. HfBounds(hf, bounds)
  589. Hf *hf;
  590. Float bounds[2][3];
  591. {
  592.     /*
  593.      * By default, height fields are centered at (0.5, 0.5, 0.)
  594.      */
  595.     bounds[LOW][X] = bounds[LOW][Y] = 0;
  596.     bounds[HIGH][X] = bounds[HIGH][Y] = 1;
  597.     bounds[LOW][Z] = hf->minz;
  598.     bounds[HIGH][Z] = hf->maxz;
  599. }
  600.  
  601. /*
  602.  * Build min/max altitude value arrays for the given grid level.
  603.  */
  604. static void
  605. integrate_grid(hf, level)
  606. Hf *hf;
  607. int level;
  608. {
  609.     int i, j, k, l, ii, ji;
  610.     float max_alt, min_alt;
  611.     float **maxinto, **mininto, **frommax, **frommin, *minptr, *maxptr;
  612.     int insize, fromsize, fact;
  613.  
  614.     maxinto = hf->boundsmax[level];
  615.     mininto = hf->boundsmin[level];
  616.     insize = hf->lsize[level];
  617.     frommax = hf->boundsmax[level-1];
  618.     frommin = hf->boundsmin[level-1];
  619.     fact = hf->BestSize;
  620.     fromsize = hf->lsize[level-1];
  621.  
  622.     ii = 0;
  623.  
  624.     for (i = 0; i < insize; i++) {
  625.         ji = 0;
  626.         for (j = 0; j < insize; j++) {
  627.             max_alt = HF_UNSET;
  628.             min_alt = -HF_UNSET;
  629.             for (k = 0; k <= fact; k++) {
  630.                 if (ii+k >= fromsize)
  631.                     continue;
  632.                 maxptr = &frommax[ii+k][ji];
  633.                 minptr = &frommin[ii+k][ji];
  634.                 for (l = 0; l <= fact; l++,maxptr++,minptr++) {
  635.                     if (ji+l >= fromsize)
  636.                         continue;
  637.                     if (*maxptr > max_alt)
  638.                         max_alt = *maxptr;
  639.                     if (*minptr < min_alt)
  640.                         min_alt = *minptr;
  641.                 }
  642.             }
  643.             maxinto[i][j] = max_alt + EPSILON;
  644.             mininto[i][j] = min_alt - EPSILON;
  645.             ji += fact;
  646.         }
  647.         ii += fact;
  648.     }
  649. }
  650.  
  651. /*
  652.  * Place the given triangle in the triangle cache.
  653.  */
  654. static void
  655. QueueTri(hf, tri)
  656. Hf *hf;
  657. hfTri *tri;
  658. {
  659.     if (hf->q[hf->qtail])        /* Free old triangle data */
  660.         free((voidstar)hf->q[hf->qtail]);
  661.     hf->q[hf->qtail] = tri;        /* Put on tail */
  662.     hf->qtail = (hf->qtail + 1) % hf->qsize;    /* Increment tail */
  663. }
  664.  
  665. /*
  666.  * Search list of cached trianges to see if this triangle has been
  667.  * cached.  If so, return a pointer to it.  If not, return null pointer.
  668.  */
  669. static hfTri *
  670. GetQueuedTri(hf, x, y, flag)
  671. Hf *hf;
  672. Float x, y;
  673. int flag;
  674. {
  675.     register int i;
  676.     register hfTri **tmp;
  677.  
  678.     for (i = 0, tmp = hf->q; i < hf->qsize; i++, tmp++) {
  679.         if (*tmp && (*tmp)->v1.x == x && (*tmp)->v1.y == y &&
  680.             (*tmp)->type == flag)
  681.             return *tmp;    /* vertices & flag match, return it */
  682.     }
  683.  
  684.     return (hfTri *)0;
  685. }
  686.  
  687. /*
  688.  * Return maximum height of cell indexed by y,x.  This could be done
  689.  * as a macro, but many C compliers will choke on it.
  690.  */
  691. static float
  692. minalt(y,x,data)
  693. int x, y;
  694. float **data;
  695. {
  696.     float  min_alt;
  697.  
  698.     min_alt = min(data[y][x], data[y+1][x]);
  699.     min_alt = min(min_alt, data[y][x+1]);
  700.     min_alt = min(min_alt, data[y+1][x+1]);
  701.     return min_alt;
  702. }
  703.  
  704. /*
  705.  * Return maximum cell height, as above.
  706.  */
  707. static float
  708. maxalt(y,x,data)
  709. int x, y;
  710. float **data;
  711. {
  712.     float  max_alt;
  713.  
  714.     max_alt = max(data[y][x], data[y+1][x]);
  715.     max_alt = max(max_alt, data[y][x+1]);
  716.     max_alt = max(max_alt, data[y+1][x+1]);
  717.     return max_alt;
  718. }
  719.  
  720. char *
  721. HfName()
  722. {
  723.     return hfName;
  724. }
  725.  
  726. void
  727. HfStats(tests, hits)
  728. unsigned long *tests, *hits;
  729. {
  730.     *tests = HFTests;
  731.     *hits = HFHits;
  732. }
  733.  
  734. void
  735. HfMethodRegister(meth)
  736. UserMethodType meth;
  737. {
  738.     if (iHfMethods)
  739.         iHfMethods->user = meth;
  740. }
  741.